# 给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
#
#  示例 1：
# 输入：a = 1, b = 2
# 输出：3
#
#  示例 2：
# 输入：a = 2, b = 3
# 输出：5

# 因为 Python 的整数类型为是无限长的，所以无论怎样左移位都不会溢出。因此，需要对 Python 中的整数进行额外处理，
# 以模拟用补码表示的 32 位有符号整数类型。
MASK1 = 2 ** 32  # 2^32
MASK2 = 2 ** 31  # 2^31
# MASK3 = 2147483647  # 2^31-1


class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 迭代写法
        a %= MASK1
        b %= MASK1
        while b != 0:
            xor = a ^ b  # 不考虑进位的情况下，加法就是 a ^ b
            # 所有需要进位的位为 a & b，而二进制都是1所获得的进位应该要放置在它的高一位上，所以进位结果还需左移一位为 (a & b) << 1
            b = ((a & b) << 1) % MASK1
            a = xor % MASK1
        return ~(a ^ (MASK1 - 1)) if a & MASK2 else a  # ~x 类似于 -x-1
        # 递归写法
        # a %= MASK1
        # b %= MASK1
        # if b == 0:
        #     return ~(a ^ (MASK1 - 1)) if a & MASK2 else a  # ~x 类似于 -x-1
        # return self.getSum((a ^ b), ((a & b) << 1))


if __name__ == "__main__":
    a, b = 2, 3
    # a, b = -1, 1
    a, b = -100, 99
    a, b = -1, 0
    print(Solution().getSum(a, b))
